package november.linkedlist.singleCircleLinkedList;

/**
 * @author huangxin
 * @date 2019/11/14-16:43
 */
public class SingleCircleLinkedListDemo {
    public static void main(String[] args) {
        SingleCircleLinkedList linkedList = new SingleCircleLinkedList();
        //5个小孩
        for (int i = 1; i <= 5; i++) {
            linkedList.add(new Node(i, ""));
        }
        int k = 1;
        int m = 2;
        linkedList.out(1, 2);
    }
}


/**
 * 单向环形链表
 */
class SingleCircleLinkedList {
    //头节点
    public Node first;

    public void add(Node node) {
        if (first == null) {
            this.first = node;
            this.first.next = first;
        }

        Node temp = first;

        while (temp.next != first) {
            temp = temp.next;
        }
        //环形
        temp.next = node;
        node.next = first;
    }


    /**
     * Josephu  问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，
     * 数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，
     * 由此产生一个出队编号的序列
     * <p>
     * 计算小孩出圈的顺序
     * startno表示从第几个开始数数,countNum表示数多少下,nums表示最初有多少个小孩
     */
    public void out(int startNo, int countNum) {
        Node temp = first;//辅助指针,用于删除节点
        //把辅助指针指向倒数第一个
        while (true){
            if (temp.next==first) {
                break;
            }
            temp=temp.next;
        }
        //first指向开始的小孩
        for (int i = 0; i < startNo - 1; i++) {
            //找到开始的小孩
            first=first.next;
            temp = temp.next;
        }

        while (temp != first) {
            //移动countNum-1下
            for (int i = 0; i < countNum - 1; i++) {
                first = first.next;
                temp = temp.next;
            }
            //此时first指向出局的小孩
            System.out.println(first);

            //删除出局的小孩
            first = first.next;
            temp.next = temp.next.next;
        }
        System.out.println("last:"+first);
    }

}


class Node {
    public int id;
    public String name;
    public Node next;//指向下个节点


    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name=" + name +
                '}';
    }

    public Node(int id, String name) {
        this.id = id;
        this.name = name;
    }
}
